COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002					 LISP
C00115 ENDMK
C⊗;
				 LISP
			   Vaughan R. Pratt
				M.I.T.
			      June 1977

<This is an article to appear in the Encyclopaedia of Computer Science and
Technology, eds Belzer et al.  [qv] refers to other articles in the
Encyclopaedia.  This article is still far from complete, but is being made
generally available to those expressing interest, to permit on-line feedback. 
Errors, both typographical and substantive, should be rife thus far; please be
systematic about rounding them up.  Please note any overlong sentences or
overly mathematical descriptions, two of my weaknesses when I'm not paying
attention.

To make the file readable, you may need to remove all occurrences of
backspace-underscore , or alternatively convert them to something that will
print as underscore or italics on your system.  S-expressions and M-expressions
are both delimited by → _.  (I print them with a fixed-width font that has
gothic uppercase and italic lower case, if you really want to see what it looks
like.  It is supposed to come out just like McCarthy's BB notation.)  Treat \ as
Greek lambda.>

CONTENTS

1.	Introduction to LISP
2. 	Language Design Issues in LISP
3.	The Mathematics Underlying LISP
4.	Program Verification in LISP
5.	Implementation of LISP
6.	Comparison with other languages
7.	LISP - Past, Present and Future

	       1.	Introduction to LISP

	The programming language LISP was developed by John McCarthy at M.I.T.
in 1959.  The name is an acronym for LISt Processing language.  Originally LISP
was seen as supplying a list-processing capability to the Artificial
Intelligence [qv] community.  A more modern view is that LISP has two facets. 
First it is a tool whose use within AI goes well beyond the data type "list" and
whose applicability to non-AI problems is slowly becoming better appreciated. 
Second, it has been the most influential language in applying ideas from
mathematical logic to programming language design, much as APL [qv] has
borrowed from linear algebra.

	There is no one source of authority on what constitutes LISP.  In this
respect LISP is unlike FORTRAN, for example, for which an ASA (American
Standards Association) standard exists.  The original system, LISP 1,
documented in 1960 by P. Fox, was soon updated to LISP 1.5, documented in 1962
by its developers, McCarthy, Abrahams, Edwards, Hart, and Levin.  This formed
the basis for an introductory text on LISP 1.5 by C. Weissman.  The numbering
1.5 was in deference to the expected appearance of LISP 2, which was to offer
algebraic notation and better numerical capability.  This project fell through
in part for lack of funding.

	The major extant implementations are INTERLISP (formerly BBN-LISP, now
maintained chiefly at XEROX Palo Alto Research Corporation), MACLISP (an M.I.T.
offspring of LISP 1.5), and UCI-LISP (an extension of Stanford LISP 1.5
developed at the University of California at Irvine).  There are also a number
of other implementations of LISP in various parts of the world, including one
at IBM's T. J. Watson Research Center used primarily for the Scratchpad symbol
manipulation system, and another at the Electrotechnologica Laboratory (ETL) in
Japan.  The following account of LISP gives a fairly accurate picture of the
common features of the major implementations.

	While it is customary to introduce a programming language by exhibiting
examples of its programs rather than its data, LISP is distinguished from other
widely used programming languages by the fact that LISP programs are LISP data. 
Thus in beginning with LISP data we will also be treating some aspects of how
one writes LISP programs.  In particular, the rules for writing LISP data
are among the rules for writing LISP programs.

Atoms

	The most elementary LISP data are atoms.  An atom is written as a
sequence of printing characters, namely the letters →A-Z_, the digits →0-9_, and
the "glyphs" →!#$%&←=@↑:+-*<>_ (give or take a glyph from one implementation to
the next).  Implementations vary on whether lower-case letters are
distinguished from upper-case; here we simply avoid lower-case letters in atom
names.

Examples of atoms.  The following are all atoms:   →3, -40, 3.1415926535,
6.023E23, T, NIL, X, INCOME-TAX, PLUS, YOU!#$%@, +, =, <-->, 1+2_.

Numbers and symbols.  The first four atoms in the above examples are numbers,
the next two are truth values (respectively true and false), and the rest are
symbols (even →1+2_).  A number is an atom written with digits, together with
any or all of a leading + or -, a decimal point, and a trailing exponent of the
form →En_ where →n_ is string of digits optionally preceded by + or -.  Any
other atom, including the two truth values, is a symbol.  →1+2_ is a symbol
because it does not meet the criteria for numberhood.

Use of atoms.  Numbers and truth values need no defense in programming.  Symbols
other than →T_ and →NIL_ are useful as variables in LISP programs.  More
importantly from the applications point of view, symbols in LISP data are
useful in programs performing symbolic, as opposed to numeric, computation,
such as simplifying algebraic formulae, proving theorems automatically,
processing natural language text, scheduling classes, playing chess, and so on. 
(It is not altogether surprising that LISP was developed at an Artificial
Intelligence laboratory.)

Lists

	Data with more structure than atoms can be represented in LISP as
lists.  A list is written in parentheses and the items in the list are
separated by spaces.  Thus →(KING LEAR)_ is a list of two atoms.  

Nested lists.  A list need not be merely a list of atoms.  It may contain lists
as well.  Thus →((A B) C (D E))_ is a list of three things, the list →(A B)_,
the atom →C_, and the list →(D E)_.  Such lists in turn may contain lists. 
Even the unlikely object →(((((A)))))_ is a list; it is a list of a list of a
list of a list of a list of an atom.  The atom A is said to be nested to depth
5 in that list.

→NIL_.  A list need not have any elements.  That is, →()_ is a permissible
list.  →()_ is also known as the atom →NIL_.  →NIL_ is the only LISP datum that
is both an atom and a list.

	Had the ancient Greeks invented LISP, →NIL_ would have been given
as short shrift as →0_, which along with 1 was not considered a number
because numbers were supposedly for dealing with pluralities.  The more
modern view is that →0_, and by the same token →NIL_, play an important role
in the basis case of inductive arguments about respectively the set
→{0,1,2,...}_ of all natural numbers and the set of all lists.  The section
on program verification contains a more detailed treatment of this issue.
Mention the BBN Swedish implementation (main for sale 370 implementation)
and Hearn's Standard LISP - PDP-10 and 370 compatible

Lists of indefinite length.  We often need to refer to lists of indefinite
length.  We write "→(a b ... z)_" to denote a list with at least one element,
"→(a ... z)" to denote any list including the empty list.  By the same token,
"→a+b+...+c_" is an expression representing the sum of one or more numbers. 
More generally, to represent →n_ or more things in a list, expression, etc, we
shall write →n+1_ variables, "...", and one final variable.

Use of lists.  Lists supply a useful way to impose structure on data.  For
example, the structure inherent in the expression "King Lear is a man" may be
captured in the list →((KING LEAR) IS (A MAN))_.  The expression "→x+y_", which
we may consider an abbreviation of "→plus[x,y]_", may be written →(PLUS X Y)_. 
(We use brackets rather than parentheses in "→plus[x,y]_" to avoid confusion
with the parentheses used in lists.)  The definite integral of the sine
function from 0 to 1 may be represented as →(INTEGRAL SIN (0 1))_.  The
contents of a room may be given by →((BED (TYPE 4-POSTER) (LENGTH 6.3 FEET))
(TABLE (COLOR WHITE) (LEGS 3) (HEIGHT 30 INCHES)))_.  The 3-by-3 identity
matrix may be represented as →((1 0 0) (0 1 0) (0 0 1))_.  The complex number
2+5i may be written →(2 5)_.

	The relationships between the characters of a novel may be represented
as →((ROBERT (WIFE MARY) (HATES (SIR GILES))) (MARY (HUSBAND ROBERT) (LOVES
(SIR GILES))) ((SIR GILES) (LOVES ROBERT)))_.  In this example the main list
contains three lists, one for each character.  The first item of each list
gives the character's name.  The remaining items give interesting properties of
that character.  Thus →(HUSBAND ROBERT)_ in the entry for Mary is intended to
say that Mary's husband is Robert.

	The electrical circuit consisting of resistors A and B in parallel,
with the result in series with resistor C, can be dealt with as
→(SERIES (PARALLEL A B) C)_.  It is impossible to represent all circuits using
just →SERIES_ and →PARALLEL_, so one may need to resort to a more general
representation, such as that based on labelling the nodes of the circuit with
numbers.  If we number the node common to all three resistors 2, the other end
of A and B 1, and the other end of C 3, then the circuit may be written
→((1 (A 2) (B 2)) (2 (C 3)))_, expressing the fact that from node 1 there is a
resistor A to 2 and a resistor B to 2, while from node 2 there is a resistor C
to 3.

	These examples illustrate the considerable versatility of lists in
representing structured data, whether or not that structure is regular or
irregular.

Programs as lists.  A particularly important usE of lists, already exemplified
above, is in representing expressions, for example "→x+y_" as →(PLUS X Y)_. 
All LISP programs are represented in this way.  This use of lists depends on
being able to view any LISP program as either a number, a symbol (used as a
variable) or as the application of a function to arguments.  The notion of
function is generalized in LISP to encompass not only the usual mathematical
functions but a variety of flow-of-control and state-manipulating operations
such as used in →(GO L)_ (a command to go to label →L_) or →(SETQ A (PLUS 1 2))_
(a command to change the value of the symbol →A_ to that of the form
→(PLUS 1 2)_).

	The representation of LISP programs as LISP data makes it possible for
one program to operate on another as mere data.  This considerably simplifies
the implementation of such program-manipulating programs as interpreters,
compilers and optimizers, for which LISP is ideally suited, efficiency
considerations aside.

On denoting

	One price for the convenience of the representation of LISP programs as
LISP data is the need for above-ordinary caution in distinguishing the program
itself from what it denotes.  This section makes explicit the standards to
which we adhere in discussing LISP programs and their meaning, as well as
introducing →EVAL_ and →QUOTE_.

	Expressions arise implicitly in our discussion, such as the expression
"→1+2_", which we might use as in "→1+2_ is →3_."  Expressions arise explicitly
in our discussion as LISP programs such as →(PLUS 1 2)_.  Expressions denote,
or have, or evaluate to, values.  Thus the discussion expression "→1+2_"
has the value →3_, as does the LISP program →(PLUS 1 2)_.

Eval.  The function →eval_ makes explicit the way in which LISP programs
denote, by mapping them to what they denote.  Thus →eval[(PLUS 1 2)]_ is →3_. 
We shall abbreviate "→eval[x]_" to "→xλ↑_".

Discussion quotes.  The presence of quotes in our discussion always means that
we are referring to a discussion expression.  It will help to think of quotes
and "denotes" as being inverses of each other.  Thus saying that →1+2_ is →3_
is the same as saying that "→1+2_" denotes →3_.

LISP →QUOTE_.  The equivalent of our discussion quotes in LISP is the form
→(QUOTE x)_, which denotes →x_ itself, where →x_ can be any atom or list, not
merely a form.  Some implementations offer the convenient abbreviation →'x_,
which we use henceforth.  Thus →(QUOTE CAT)_ denotes →CAT_.

	This LISP quoTe is the Inverse of →aval_.  Hence the LISP program
α→(EVAL '(PLUS 1 2))_ may be used instead of the LISP program →(PLUS 1 2$0\@~))QSf↓GC\A	JAeKAKCiK⊂XAg↑↓iQChαe"⊗4
1↓≥D*Zε1α9"⊗Za↓≥"∧bVM↓
↓I%%JHaβπv 4(eD*Zε1αB⊗Zεb↓"⊗Za↓≥≥:BB2V~↓E↓IJI%$aεK∃β⊗{S!β/W'[∞c↔;Q∧εFz↓∃
∧e-4ε∩β∩∪∧ε∂_Q)DM≥∧∞π⊗}},⊗o~d∧∧∂~	I∃≥αL↔&
∞Mε/J≡&*εm}Bπ&Tπ≡∞\UBεF}|W6/%aPPh)l⊗n/5dα∧∞dWGπ,↑7≡N⎇eBπ>↑FF/$λ
-d≠⎇<D~<xn↑|z;md≠|H
≥H∪∩*:λ∪,∨(_p↔[:0twλ70vr\FE7cλ80y:~qzv0\⊂:44[3yV⊂≠y⊂7sλ4s22Y4w4`4e things.A)QKMJA]C5KfACIJAGC1YKH~)eKgaα+∂S'6+3eβ≤{;OS∞sSMβ∞s⊃β[∂∪'πf+M8∀Ph*∂?w≠Sπ;'→9↓α/Cπ7Cd+Mβ?2β∂?;∨#π;S~β↔;∂␈+;C↔⊗+⊃βπdε&.∞O∀εNrM↔≡∨↑>6N}d↔⊗*∧#∪→B%APR⊃_8∃!B%Dα⊃J
	E-~ε∀β∩I∧!Bε∞lDα⊃O
NW→B%Dε&.mx

≥Yh≤L↑|→8nM=Y;∂∀_(≠N]8Y<ED_#"N?;8[mEλ_(
M<⎇β∧;Yλ∀→];L>~;{Edλ∃~T_{|N,<|∪ml~;Yd	∩4t∧{{\nL;]≤d<Y(β⊗fβ!#)pp*Cλε$u∀∪∃*4(E∪λ⊂-lλε*λj3Pu	→sH∀	J4j&¬dλ
∀l\(≥~T≠Y>∞D≤y8nM;{K∧
{C"Ln;X⎇
≥{\k∧[|H∀→~<l><|z-⎇H≠yD∧F<≠∞↑fλH∞l<\u.4ε*⊃JYPu∩)yH∀∪
Zj&E⊃"C"Jl<Z8,-→<kD∧∩;H
}<H→
≡x⎇<n=;{H∞l<Z8,-→<h∞⎇;≠λ≥≥x>.4_Y(∞}Z=≥]H_<d∞z;YmL(~=≥~8c!-→=≥↑\h≤n\zλ_.4λF8#∧H_;LDλF>β∧KHλ	≥H∪∩*:λ≥X.-88[↑h≠8/∀_Y(≡XZ=∞,<↑(∞?;8[mNc"\n\zλ_.4ε6ε∧;Yλβ→3PsiX+5⊂+βC"AQPZ;LM;YkD∧⊂<h∀∪∩4j∧≤≤[l}X;+∧(≤}-\[{λ
\>(≠n$≠8>$
[⎇λL;[⎇T_(≥L≥≥9.d∞z→;D
=β"LMy<h
≡λ~<d∞x:9∧∞≠h_LT_[⎇-lλ≥≠d∞~_=∧∞X;≥,Uλ≠⎇
<]z.<(~=∧
<h≤l≥9λ≥
t_Y(∞]X[⎇-lHβ!*~≥<d
9Hε+βλ~<d[⎇;LD≥≠h∞M→(≥L≥≥9(ε∀
_(
n;8Y.%(_;LDε6&∧∞≠h≥
(≥X-N9(ED≥~→-d~;C!#*∀∪
Zh⊗λ∃&λε+βλ→→-m⎇→<dε(_;LDε6&∧→;[nL<hEdλ∪;n>λ≤}-\[{≤d<Y(
≥Z=~,≥≠≡#!.;X[n]Yλ≥m;H_$∞<y<DY9z-nh_;D
;]→.,8⎇~.l(≤y.>z;{D∞z=~∧	∩4t¬dλ⊂Z-l~;Yd
<h≥.<9β"NMh~;.
→;9-nλ_[nMλ≥~T≥<⎇,≥λ≠[nM;{H
|H_<n=9{[,]]λ≥
t_(≥L≡Z88ML(_;LD≥~→!QX<|m≤{[9-nλ≠yD<Y⎇-\;]λ∞l;≥9.4≥≠hm|[8-D≤_<L≥9=→..h~;D];XnM;{HL9Z;M≡~;{N5β"\∞-xy<n<<h≥
=λ≥lT≥z;
D_{{N=9→<D
_=→.%ype restrictions.  Any symbol may be bound to any value.  Symbols are not
restricted to particular types, in contrast to most other languages where
variables are either explicitly declared to be of type integer, real, Boolean,
etc, or are implicitly typed, as in FORTRAN where the first letter of the
variable's name gives the type.  Some LISP implementations permit "hints" to
the implementation (specifically, to the compiler) of the form "You may assume
that X will only take on integer values."  However these hints should not be
construed as part of the definition of the language proper.

Environments.  An environment is a collection of atoms together with their
bindings.  The value of "→eval[X]_" clearly depends on the binding of the
symbol X, and hence on the environment.  All evaluation in LISP takes place in
the current environment, which can change during evaluation whenever symbols
are rebound.  Some implementations offer representations of environments, and
permit →eval_ to take an environment as a second argument.  The evaluation is
then performed in the given environment rather in than the current environment.

Functions and Predicates

	Functions play an important role in computation, providing a means of
producing new and interesting objects from old.  Predicates are necessary to
permit the program to make choices based on relevant properties of the data in
hand.  Numerically oriented programming languages offer a wide range of numeric
functions and predicates such as →plus_, →times_, →sin_, →equal_, etc.  Since
LISP deals not only with numbers but with symbols and lists, it must offer a
wider variety of functions and predicates.

	In our discussion we shall refer to functions and predicates in any of
up to three ways.  For example, we shall use "→plus_" to denote the addition
function itself, "→plus[x,y]_" to denote its application to →x_ and →y_, and
"→x+y_" as a convenient abbreviation of "→plus[x,y]_."  Not all of the
functions we consider will have abbreviations.  "→plus[x,y]_" itself may be
considered an abbreviation of "→apply[plus,(x y)]_," where →apply_ is a
functional taking two arguments, a function and a list of arguments to apply
that function to.  (A functional is a function taking as argument another
function, rather than a more ordinary object like a number or a list.)

	In LISP programs the function →plus_ is denoted by the LISP form
→(FUNCTION PLUS)_, while its application to arguments →x_ and →y_ is denoted
implicitly by the LISP form →(PLUS X Y)_ and explicitly by →(APPLY (FUNCTION
PLUS) (LIST X Y)).  Note that →FUNCTION_ is required when naming the function
→plus_ itself, but not when implicitly applying →plus_ to arguments.

Functions on numbers.  LISP offers a modest collection of numeric functions and
predicates.  All of the following functions should be familiar to the reader;
we tabulate them here mainly to specify the LISP representation for them, and
to remark on properties of them that are peculiar to LISP.  (Recall that
"→aλ↑_" is our abbreviation for "→eval[a]_.")

→(PLUS a b)		 aλ↑+bλ↑	   (TIMES a b)		aλ↑bλ↑
(DIFFERENCE a b) aλ↑-bλ↑	   (QUOTIENT a b)	aλ↑/bλ↑	
(MINUS a)		 -aλ↑	   (EXPT a b)		aλ↑↓#∞bλ↑↓#
(ABS a)		 |aλ↑|	   (REMAINDER a b)	aλ↑ mod bλ↑_	(see text below)

	LISP supports fixed point (integer) and floating point (real)
arithmetic.  The functions →FIX_ and →FLOAT_ may be applied to any numeric
quantity to coerce it to the appropriate type.  The type produced by an
arithmetic function is real when one or more of its arguments is real (this
rule is affectionately called "contagious floating point"), otherwise it is
integer.  This applies even to →QUOTIENT_, which given two integer arguments
produces the closest integer to the answer whose absolute value does not exceed
that of the answer.  (This definition coincides with current practice in the
computer world but not the mathematical world, which omits "absolute" in that
definition.)  However →REMAINDER_ does satisfy the identity →a = qb+r_ where →q
is the value of (QUOTIENT a b)_ and →r is the value of (REMAINDER a b)_.  Thus
→(REMAINDER -1 3)_ evaluates to -1_.  The mathematical definition would give →2_. 

	Most implementations permit →PLUS_ and →TIMES_ to take any number of
arguments, with the obvious meaning in each case, and with →(PLUS)_ (no
arguments) taken to denote →0_ and →(TIMES)_ →1_.  Some implementations (e.g.
MACLISP) support multiple precision integers ("bignums"), invoking the
appropriate routines when overflow is detected so that no user intervention is
required.

Predicates on numbers.  As in any programming language, it is necessary for a
program to be able to test interesting properties of its data.  LISP offers the
following numeric predicates.

→(EQUAL a b)	 aλ↑=bλ↑	   (MINUSP a)		aλ↑<0
(LESSP a b)	 aλaλ↑<bλ↑	   (ODDP a)		aλ↑ is odd
(GREATERP a b)	 aλ↑>bλ↑	   (ZEROP a)		aλ↑=0_

	There is also a predicate →(NUMBERP a)_ which tests whether →aλ↑_ (which
obviously need not be numeric) is a number.

Functions on atoms and lists.  Just as one can combine numbers using arithmetic
functions such as →plus_ and →times_,  so can one combine atoms and lists using
list functions.  The two basic functions for decomposing lists are →car_ and
→cdr_.  If →x_ is a non-empty list then →car x_ is its first element and →cdr
x_ is the list of all elements of →x_ but the first.  Thus →car (WE FREE FLEAS)_
is →WE_ and →cdr (WE FREE FLEAS)_ is →(FREE FLEAS)_.

Car and cdr.  The expression "→car x_" may be written in LISP as →(CAR X)_,
just as earlier we saw "→x+y_" written as the LISP list →(PLUS X Y)_, and just
as we would write →(SIN X)_ for "→sin x_" and →(CDR X)_ for "→cdr x_".

Cons.  The basic function for constructing larger lists from smaller is
→cons_.  If →y_ is a list then →cons[x,y]_, or →x.y_ as we shall abbreviate it,
is the list whose →car_ is →x_ and whose →cdr_ is →y_.  Thus →WE.(FREE FLEAS)_
is →(WE FREE FLEAS)_, while →(KING LEAR).(IS A MAN)_ is →((KING LEAR) IS A MAN)_,
not →(KING LEAR IS A MAN)_.  In general →x.(y1 ... yn)_ is →(x y1 ... yn)_. 
The LISP for "→x.y_" is →(CONS X Y)_.

	There is a rather trivial function called →list_, which forms a list
from its arguments.  Its triviality is emphasized by the abbreviation of
→list[x,y,...,z]_ to →(x y ... z)_.  In effect this permits us to think of
→(I AM n)_ as →list[I, AM, n]_, that is, the result of applying →list_, (the
function represented by the parentheses of →(I AM n)_) to the three objects →I_,
→AM_, and the value of →n_.  The reason we need to identify the function →list_
explicitly in this way is that in representing LISP programs as LISP data,
every function must be made explicit as the first element of a list.  Hence we
should write →(LIST 'I 'AM N)_.  In the special case when all the arguments
to →list_ are constant, as in →(I AM FRED)_, we may more conveniently write
→'(I AM FRED)_ instead of →(LIST 'I 'AM 'FRED)_.  However, this use of →QUOTE_
does not work when one or more of the arguments are expressions containing
variables such as →n_.

	The function →append_ joins several lists into one long list whose
elements are those of the original lists.  It can be thought of as a variant of
→list_ which first strips off the outermost pair of parentheses from each of its
arguments before forming a list from them.  We shall abbreviate
→append[x,y,...,z]_ to →x@y@...@z_.  Thus →(KING LEAR)@(IS A MAN)_ is
→(KING LEAR IS A MAN)_.  →(HERE IS)@NIL@(THE)@(ONLY (STRONG MAN))@(LEFT)_ is
→(HERE IS THE ONLY (STRONG MAN) LEFT)_.   Notice how the empty list →NIL_, as
an argument to →append_, has no effect on the result.  Also note that if some
list element is itself a list, as is →(STRONG MAN)_, then it will still be a
list in the result.  Some degenerate cases are →append[a] = a_ and →append[] = NIL_.

	In comparison with →list_ and →append_, →cons_ seems an odd fish.  It does a
little of the work of each of →list_ and →append_.  Consider again
→(KING LEAR).(IS A MAN)_, which is →((KING LEAR) IS A MAN)_.  →Cons_ appears to
treats its first argument as →list_ does and its second as →append_ does.  In
fact, →cons_ seems quite redundant, since →x.y_ can be expressed as →(x)@y_. 
The importance of →cons_ is that it is an easy-to-implement primitive which can
be used to define both →list_ and →append_.  Let us first deal with its
implementation, which gives an opportunity to talk about S-expressions at the
same time.

S-expressions

	A little thought will show that →a.b_ is not a list when →b_ is not a
list.  One way this may happen is if →b_ is an atom and is not →NIL_.  However,
→a.b_ is defined, and its →car_ is →a_ and its →cdr_ →b_.  There arises the
question of how to write the result of such an operation.  When b is a non-null
atom →a.b_ is written in LISP as →(a . b)_.  Hence →FEAR.NOT_ is written
→(FEAR . NOT)_.  When →b_ is neither an atom nor a list, but can be constructed
from atoms using only →cons_, then →a.b_ can be written by writing the first
parenthesis of →b_, then →a_ followed by a space, then the rest of →b_.  (This is the
same rule one could use even when →b_ is a list.)  Thus →FEAR.(ME . NOT)_
can be written →(FEAR ME . NOT)_.  Alternatively it can be written →(FEAR . (ME . NOT))_,
but the former is preferred.

	If →(FEAR . NOT)_ is neither a list not an atom, then what is it?  We
need the notion of a data-type where cons can be applied indiscriminately.  The
data-type S-expression includes all the atoms together with everything one can
get by applying cons repeatedly.  (A mathematician would say that the set of
S-expressions is the closure of the set of atoms under cons, just as the
set of natural numbers is the closure of the set {→0_} under successor.)  In
particular, all atoms and all lists are S-expressions.

Computer representation of S-expressions.  Before reading this section the
reader may wish to study the entry in this encyclopaedia on List Processing.) 
We have already seen the representation of S-expressions on paper.  Inside the
computer S-expressions are represented altogether differently.  All
S-expressions (with the exception of small numbers in some implementations) are
represented as pointers to locations in memory.  A numeric atom points to a
location containing its value.  A non-numeric atom points to a list of the
atom's properties.  The result of evaluating →(CONS A B)_ is a pointer to a
location containing a pair of pointers.  The effect of →CONS_ is to construct
such a location.

	We now consider the problem of using →cons_ to define →list_ and
→append→.  The following equation serves to define →list_; we shall treat
the LISP representation of this definition later when we have more artillery.

→list:   () = NIL (i.e. list[] = NIL)
        (a b ... z) = a.(b ... z)_.

	It follows from this definition of →list_ that any list may be
constructed by starting out with →NIL_ and building up the list from right to
left using one application of →cons_ for each list element.  Thus we can
build up →(a b c)_ by starting with →NIL_, forming →(c)_ as →c.NIL_,
then forming →(b c)_ as →b.(c)_, and finally forming →(a b c)_ as →a.(b c)_.

→append: NIL@b = b			_(two-argument →append_)→
        (x.y)@b = x.(y@b)_.

	This definition of →append_ depends on being able to reduce the
problem of forming →a@b_ to the smaller problem of forming →y@b_ when y is
the →cdr_ of →a_, provided →a_ is not →NIL_, a case provided for
explicitly.  To extend the definition to three or more arguments it suffices to
have the rule

→        a@b@c@d@...@z = a@[b@c@d@...@z]_.

	Three other functions are of interest:  →reverse (a1 ... an)_ is
→(an ... a1)_,  →length (a1 ... an)_ is →n_, and →subst[a,b,c]_ is the result
of substituting →a_ for every occurrence of →b_ in the list →c_ (including
occurrences within nested lists of →c_ but leaving the original copy of →c_
unchanged).  In LISP one would write respectively →(REVERSE a)_ to form the
reverse of aλ↑_, →(LENGTH a)_ to get the length of aλ↑_, and →(SUBST a b c)_ to
substitute aλ↑_ for bλ↑_ in cλ↑_.  (Recall that →aλ↑_ denotes the value of →a_.)

Use of list functions.  These functions are useful when programming in LISP to
build up lists and to access their elements.  While the particular list
→(KING LEAR)_ is something that can simply be written as is, a list whose
elements are unknown at the time the programmer is preparing his program cannot
be written in this way.  If the programmer wants to construct a list whose
→car_ is →THE_ but whose →cdr_ is entirely unknown other than that it is the
value of the variable →x_, then he needs →THE.x_, and thus should write
→(CONS 'THE X)_ in his program.  This is just the same problem that one
encounters with numbers.  One wants to add →2_ to the value of →x_, but not
knowing that value when writing the program one must write →x+2_, or in LISP
→(PLUS X 2)_.

Predicates on lists and atoms.  The basic predicates are →equal_, →atom_, and
→null_.  →equal[a,b]_, or →a=b_, holds just when →a_ and →b_ are the same atom
or the same list.  →atom[a]_ holds when →a_ is an atom.  →null[a]_ is
equivalent to →a=NIL_.

Eq.  There is also a predicate →eq_ which plays two roles.  First it permits
testing equality of atoms, which is a useful primitive if →equal_ itself is not
given as a primitive.  Secondly, it has an implementation-dependent aspect,
namely that →eq[a,b]_ holds when →a_ and →b_ are not merely the same list but
in fact the same representation of that list.  It should be clear that →eq_
can be thought of as testing pointer equality.  This makes →eq_ very easy to
implement.  →equal_ can then be defined in terms of →eq_, just as →append_ and
→list_  can be defined in terms of →cons_.  This establishes the_ importance of
→eq_ as a primitive along with →cons_.

Truth functions.  It is a peculiarity of LISP that those of its functions that
expect truth values will in fact accept any S-expression, treating →NIL_ as
→false_ and all others as →true_.  Though all LISP predicates, and the Boolean
function →NOT_, return only →T_ or →NIL_, the functions →AND_ and →OR_ (taking
arbitrarily many arguments) return respectively their first null argument or
their first non-null argument, taking the last argument if no earlier one was
satisfactory.  If →AND_ and →OR_ are only given the truth values →T_ and →NIL_,
then this agrees with standard usage.  However, an alternative interpretation
for →AND_ and →OR_ is possible in the more general case; thus →(AND a b)_ may
be interpreted as "a, AND if so then b, otherwise →NIL_," while →(OR a b)_ may
be read "a, OR failing that, then b," where →NIL_ is considered failure.  For
example, →(OR (F X) (G X)_ would return the value of →(F X)_ without evaluating
→(G X)_ unless that value was →NIL_, in which case it would return the value of
→(G X)_, whether →NIL_ or not.

Conditional expressions.  The value of the form →(COND (a1 b1) (a2 b2) ... (an bn))_
is the first →bλ↑i_ whose corresponding →aλ↑i_ is true (i.e. not →NIL_). Thus one
would write →(COND ((MINUSP a) (MINUS a)) (T a))_ as an alternative to →(ABS a)_. 
The process of evaluating a →COND_ is to evaluate each →ai_ in turn until
something other than →NIL_ turns up, and then to evaluate the corresponding
→bi_.

	The list (ai bi) is sometimes called the i-th clause of the conditional
form.  In some implementations each clause can have more than two elements, in
which case if the first element of the clause evaluates to non-NIL then all of
the remaining elements of that clause are evaluated.  Thus
→(COND (a11 a12 ... a1j) ... (an1 an2 ... ank))_ would correspond to
"→if a11 then (a12;a13;...;a1j) else ... else if an1 then (an2;an3;...;ank)_."

Lambda Expressions.  So far every expression we have been able to write has
denoted either a number or a truth value.  We have been able to use the
functions already offered by LISP, bu@PAQCmα)β;?"β↔↔rβπ3*βS=β&+≠';*β≠W;∨#'?;_h+?→ε{WIβ␈;99↓∧K9β7␈≠Qβ?&C↔Iβπ∪?∨K∞k7';:β3π;?+π∨↔~aβ∪↔6K;';:β;↔]∧3W;∂&K?;MεKL4+∞≠∂?7εc'O#.!βeπ≠?7∃ε≠?;O'∪W∂Qε{→βSF)β≠?⊗i↓∪.3';∃ε1#aEbq993Fq%↓u∧)#aEbq9;crIλ4+>C↔K∃∧)β'Mπ≠?7∃ε+cCK/≠O'?rβK↔≠/∪K';:βS=β&C∃β≠.s∂S'}sMβπ⊗;W7↔w#Mβa
a999gC99↓¬#←<4W##';?→β#π4∧RεF≡λ]Y9λ
<Y.d(→]-l⎇~;md~_<dY9;D→9R-l9λ≥Yλ~.D~_<dY9;Dz=Y-d_#"Ml;9+D∧∃~→$Z<\nD≠yH∞M→<q$≠y<d
[⎇λ
≥][s∞l(_;O∀≠[⎇
≥{H≠ld≠88m
;Y(∞>_=→%D_<c!,];XnM;{\d
_=P∩H0w⊂0X9z90Xz⊂2|~yz2w_rP4w→2x2w→2w:⊂≠s⊂0P_wvx:]2y∪yH6rvw\<V⊂5≥yzεE_yP27H7:vq→y9W⊂λ$7{r]2y⊗⊂≥42P9Yqww2λ4vx6~ryP:~0z⊂9[vrP1Z0w3rH7s⊂9]0z2P≠s⊂0FB6pqt~w2P4_yP40\82w2Y⊗⊂0w→⊂:40]⊂4w⊂→:z:y→P0w<H92s2\2w1rH:7P3λ6p|P_2P:0Zrw⊂:≠P12FB0P92Y2y2w_rP:7H:42P→:w1z~ww⊂7≠{P0y\wqtp]2r⊂;Zz4⊂3εEεEαf$ihλ6pur\P:44\P24y]4w1z~ww⊂1≡P82y≠tz:4[3P3:[1z4w[9P:7H12P2→s4w2YεE;t]47zzλ0yywXtpz4[3P:4→vP;t]4⊂0w≡P80y≥4qzv_y⊂70[rW⊂⊂∃42P:→qt74\zrP3≠y⊂27Zw3FE≥44yP≥pyP2→{2v7\2r⊂1≡P:42H67stXtpw⊂⊂v7w=≠P!t:\1t⊂4[⊂:42H_\YX	yV⊂0[2⊂3p]2P94\rFE:≠P0P9]q52q]⊂:40]⊂1pvYP:7P_2P5w≠{w⊂0\P:42H60vq→0P1p[1zv:\P-x{↔WαEεB∧j42H3rw2\0v⊂3≠y6P7Y⊂0P6_vq20Kr|89→yytw[⊂4w⊂∪$ih⊂~yFEJ& fa⊃ P∀<P↔↔↔λ<7∀P_∀L⊂;Z2y2Pε|_L≥497zYt⊂|≠⊂0y→P9|vX7v9P_w2⊂X⊂4yH0P37\6W⊂εB+t2y→{2y⊂_P3:w_z4wwλ9zqtλ0yPT&*iLλ7y⊂S$ijλ6p|P_2P:yYr⊗⊂9[P6p|H0FE6_vq20Kr|89→yytw[↔εEεB∧j42H;0v:YP7s⊂≥42P3≠y6PJ∀& fP" P∀≡_P↔↔⊂<7∀H1∀P0LP↔↔↔λ0w∀Lλ4yP:~2P;0[:rFE≠s⊂qε⊗⊂:0Ztw3P≥42P;_v:rP≠s⊂2pXt⊂|~L⊂4wλq⊂
:yrrλ4w⊂X⊂;t→y2{2\⊂0P3≠y6P6X|FE1→P:yrY∀P:7H12P:~0z⊂7Y⊂0tWλ⊂+rP≤p|P:~0z⊂↑_L⊂:~97zsZ⊂|7ε⊂0y2H60vq→0Vq7]w2⊂:≠FE:4→P;0v≥ryP7Y⊂pXF⊂:49≠zst⊂εpw⊂≤2yx2Xz4{2[<W⊂⊂⊃7y⊂2↑0vx6→V⊂:4→P3:w_z4wwβET&⊂fa" H∀,∀P
(&*iH,⊂→TJL⊂4yH0P3:[1z4w[⊂:40]⊂0r2≤PYLλ:7P4]9P7w→P0y3]vrw:∞P:4:\FET
& fa⊃ P∀,
P∀(&∃iP,⊂TTP~JL⊂;w]v2⊂2]0v:p]2P:7H\↔βEεE∧PPf Sa" Lr|89→yytw[⊂4yP≠7z⊂0H37y6K⊂0w2λf fP" L⊂~yP77]⊂0P3≥w1z4[w↔⊂εBf fP" L⊗Y|892\ytww≤P6p|H7w6<H12P:\rr⊂;Z2y2P≥42|P≥tv6⊂_2P4w≥2y89→z2r⊂_yFE3≥w1z4[w9W⊂λ)wP3_y⊂;rH40{"H7w6<H9rrwλ7w2P≤60qrH;t2y→P:44\P;tv≠⊂40x≤2w⊗⊂≠0vrv≡P4wεB:42P→:w1z~ww⊂8≠ytz4[w⊂7sλ0P37\6P∀1≥z⊂9rYPc*S!j$gS⊂12[7{TWβEαE#≤2rP0[2⊂17]w2⊂7Xqzy9→w1ry\W⊂⊂+YP9p|H:40zλ|_Lλ:497]st⊂↑7⊂7Xqzy⊂_7zw2λ4wεEεT& fP" P∀≡_P↔↔⊂<7∀H1∀L↔λ⊂ v6λ7z42\⊂77ww:vr\4qP0]7vyP~w⊂qε⊂77zλ7qqz\94w3CE17z[2⊂4wλ9wvrH9zq2↑892y\tww⊂≠s⊂qε⊂0y2H9ptrλ:7P7Xqzy⊂→92rP~wεEJ& fa⊃ P∀<P↔↔↔λ<7∀P_∀L↔εBεE∧kYP9ptY⊂2py≠4ry⊂≥40z≤:y2P∪$ih⊂≥pyP:~0z⊂8_y:⊂7Y⊂&$iT⊂;t4Xt⊂1w]v2⊂7≠zεE1XzyrP≤tr2VYs32q]9V⊂:~0z⊂4\V⊂1w]v2⊂'≠z⊂82\6pw2[:6<P_t0w3YP:42H2w;4\7w6r[:εE∀≥47zsZ⊂:2v\7y0y≡P1t0[3ryP_y2P8≠yytq≠2P:yZw3P6_vq20Kq4w2~w3TWλ⊂ P1[0tvrYεE12[2s4zλ;pyP≥42P6_quP7Y⊂:w2↑82qz→r⊂4w≥2y0q]4ww⊂_2z;rYw⊂92[wz2P≤97sy_vyV⊂→:rP:≠FE7w→P897Yy0vP_t0w3Zw3P:~2P;0[:rP7Y⊂0w⊂_z7vP≥yrr_<P0w≠z42yλ897s\0vWλ qqw\24w3CE:7P≠zy⊂"→s4w4]4ww≠q⊂2w≥4y7w≠rw:⊗λ92vw]2P4w≥2y0q]4ww⊂~yP9j~v6⊂8≠yytq≠2P;4XP:42CE60vX20Vq~w24w→P4w⊂≠w2P3≥w1z4[w⊂7sλ0P;0\4pq6→P:ybY⊂4w⊂_w7z4→y⊂3:[1z4w[⊂1pv≠2rεE
87yyZq6<P≥2y<P~w24y→qz6<JP1<P≥42P3~y9z⊂→:w1z~ww↔⊂λ*42P→w;4i≠w6rw≥⊂4w⊂≥t4qtλ:42FB60vq→0Vq4[24w3H;pyP→7w2P≠p|P9]4v6⊂~0{2P≥40z_4w24[3P;t→w⊂:4→P1pv≠2r⊂3≥w1z4[w⊂4yCE2{0[:pz2Y⊗⊂;t~qt⊂6X|P7yλ6p|P≠7z⊂4_{2P1→rw⊂;Z0z⊂:~2P:yYy⊂4w≥2w22Y≥P4zλ4yFE→4s34Xzv:⊂≥7P5rYx⊂:9_quP7Y⊂0v6λ:yryH7s⊂0H3t{2[⊂;0y~ throughout a large
program.  Thus a more complete definition of pure LISP would forbid variables
occurring free in lambda-expressions.

Recursive LAMBDA.  It is possible for a function defined using →LAMBDA_ to refer
to itself, thus permitting recursive definitions, with the help of the →LABEL_
construct, which like →LAMBDA_ is not a function but rather a way of constructing
functions.  If →l_ is a lambda expression wishing to refer to itself as the atom
→f_, it may do so by being written →(LABEL f l)_.  As a simple example, we may
multiply the numbers 23 and 37 using only the arithmetic function →PLUS_ and the
predicate →ZEROP_, with

→((LABEL M (LAMBDA (X Y) (COND ((ZEROP X) 0)
			      (T (PLUS Y (M (PLUS X -1) Y)))))) 23 37)_

	This recursive definition of M as multiplication relies on the two
facts →0x = 0_ and →y+[x-1]y = xy_.  Note that M is local to this expression,
just as are the lambda-variables →X_ and →Y_; the use of this expression has no
bearing on the meaning of M in other expressions.

	All of this would create no problem were it not for the fact that it is
often convenient to be able to manipulate functions as mere data, for example
passing a function as an argument to another function (or functional, to be
precise).  For this purpose there exists the pseudo-function →FUNCTION_ which
takes as argument a form →f_ that could appear in the first position of an
S-expression and yields as value what →f_ would be interpreted as in that
position.  Thus →(FUNCTION PLUS)_ would denote →plus_.  →(FUNCTION (LAMBDA (X)
(PLUS X 2)))_ would denote the function that adds 2.  FUNCTION_ is only of
significance in programs, and need not be used in our discussion to refer to
→plus_.

	The implementation of →FUNCTION_ is identical to that of →QUOTE_ in
many systems.  Thus one could equally well write →'PLUS_ where →(FUNCTION PLUS)_
was called for, and the system would be none the wiser.

	The problem now arises as to how we are to use such objects as
functions.  That is, how are we to represent the result of applying say the
value of →(FUNCTION PLUS)_ to the arguments 1 and 2?  If the S-expression →f_
denotes a function, the S-expression →(f x)_ does not in all implementations
denote the application of the value of →f_ to the value of →x_, (though in some
implementations this is provided for).  The functional →APPLY_ permits
functions that exist in this form to be applied to a list of its arguments. 
Thus if the value of the form →f_ is the function →PLUS_, then →(APPLY →f_
(LIST 1 2))_ would have the same value as →(PLUS 1 2)_.  Since →(FUNCTION
PLUS)_ denotes the addition function, →(APPLY (FUNCTION PLUS) (LIST 1 2))_ also
denotes the same thing, as does →((LAMBDA (F) (APPLY F (LIST 1 2))) (FUNCTION
PLUS))_.

	A novel use for →APPLY_ is to form the sum of the elements of the list
→x_, using →(APPLY (FUNCTION PLUS) x)_.  For if →x_ were →(3 5 9)_ then this
would be just as though we had written →(PLUS 3 5 9)_.  Likewise we can compute
the product of the elements of a list, using →(FUNCTION TIMES)_.  If we want to
tell whether a list does not contain →NIL_, an alternative to →(NOT (MEMBER NIL
x))_ is →(APPLY (FUNCTION AND) x)_.  →(FUNCTION OR)_ will permit testing for
any non-→NIL_ element, and will return the first one if there is one.  Some
implementations have →MAX_, →MIN_, →GCD_ and other associative functions that
may take arbitrarily many arguments, and the same technique may be applied. 
For example, →(APPLY (FUNCTION MAX) x)_ will return the largest number in the
list →x_.  When →LESSP_ is implemented so that (LESSP a1 a2 ...
an)_ is equivalent to →a1<a2<...<an_, then →(APPLY (FUNCTION LESSP) x)_ tests whether →x_ is
an ordered list of distinct numbers.

	Another use of functions as data has to do with the function
→mapcar_.  This function (strictly speaking, a functional) is useful for
applying a given function to all the elements of a given list.  Thus
→mapcar[MINUS, (1 2 3)]_ (represented in LISP as →(MAPCAR (FUNCTION MINUS) '(1 2 3))_
is the list →(-1 -2 -3)_.  In general →mapcar_ takes as its first argument a
function (of n arguments) and as its remaining n arguments (the same number n)
lists of values to apply the function to, returning the results in the form of
a list.  (In some implementations n is restricted to 1 and the two arguments
are given in the other order.)  Thus →mapcar[PLUS, (1 2 3), (4 5 6)]_ is the
list →(5 7 9)_, just as though the lists were being added together as vectors. 
In full generality,
→   mapcar[f, (x11 x12 ... x1n)  (x21 x22 ... x2n) ...  (xm1 xm2 ... xmn)]_
would be the list
→           (f[x11,x21,...,xm1] f[x12,x22,...,xm2] ... f[x1n,x2n,...,xmn])_. 
(Readers familiar with matrix algebra may visualize the m lists as the m rows
of an mxn matrix.  Then f is applied to each of the n columns to yield a list
of n items.)

	One way to think of →mapcar_ comes from thinking of lists as functions
from numbers to list elements, where the number indexes into the list.  Thus
the list →(3 1 4 1)_ may be considered to be the function that maps 1 to 3, 2 to
1, 3 to 4 and 4 to 1.  (This is not to say that LISP will let you apply lists
as though they were functions.)  Then →mapcar[f,x]_ forms the composition of f
with →x_.

	A conceptual use for this way of thinking about →mapcar_ is as follows. 
To apply two functions, say →f_ and →g_, in turn to each element of →x_, to yield
(f[g[x1]] f[g[x2]] ... f[g(xn]]), one way is to form the composition of f and g
and use →mapcar[\z.f[g[z]], x]_.  However, it is not hard to see that another way
of accomplishing this is with →mapcar[f, mapcar[g,x]]_.  This can be thought
of as an application of the associativity of composition.

	Combining →MAPCAR_ with →APPLY_ can lead to some powerful constructs.  For
example, to test whether the list →x_ contains a negative number, use →(APPLY
(FUNCTION OR) (MAPCAR (FUNCTION MINUSP) x))_.  To transpose a matrix →m_
represented as a list of lists, use →(APPLY (FUNCTION MAPCAR) (CONS (FUNCTION
LIST) m))_.  (This approaches the obscurity of similarly "clever" APL
programming!  We do not necessarily recommend this as a programming style.  The
point is that these operations are very powerful.  Whether such uses are
considered abuses is a human engineering issue.)

Other maps.  One possible variation on →mapcar_, called →maplist_, is to apply
→mapcar_'s first argument not to the list elements but to the list "tails",
that is, to the list itself, then its →cdr_, then the →cdr_ of that, and so on
up to but excluding the empty list Thus →maplist[f,(1 2 3)]_
would be →(f[(1 2 3)] f[(2 3)] f[(3)])_ rather than (f[1] f[2] f[3]).

	Another variation, →mapcan_ (or →mapconc_ in some implementations)
has the effect of →mapcar_ followed by an application of →append_ to the
result.  That is, →mapcan[f, (1 2 3)]_ is →f[1]@f[2]@f[3]_.  This is useful
when each application of →f_ is to produce, not a single value but a list of
values.  As a special case of this, →f_ may need to produce either no values or
one value.

	A third variation, →mapc_, simply discards the result (or more
accurately, does not form the result in the first place), returning →NIL_
instead (or in some implementations the value of its second argument).  It is
used only for its effect, a concept depending on the process model of LISP that
we discuss later.

	"To iterate is illiterate, to recurse is worse.
	 To avoid this trap, see instructions for →mapc_."

	The function →mapcon_ combines the →mapcan_ variation (appends results)
with the →maplist_ variation.  The function →map_ combines the →mapc_ variation
(returns →NIL_) with the →maplist_ variation (operates on tails).

	In summary, these six functions are

		Elements	Tails
list:		→mapcar_	→maplist_
append:	→mapcan_	→mapcon_
→NIL_:		→mapc_		→map_

LISP Programs

	As we have already seen, certain lists have a special meaning to LISP
For a list to be a program, or form as it is often called (we shall use
program and form interchangeably), it must be one of the following:

(i)	an atom;

(ii)	a list whose first element can be interpreted as a function and whose
remaining elements are forms;

(iii)	the list →(COND c1 c2 ...cn)_ where each clause →ci_ is a list whose
elements are forms;

(iv)	the list →(QUOTE s)_ where →s_ may be any S-expression.  (We take
→'s_ to be merely a convenient abbreviation of →(QUOTE s)_, whence this
case covers →'s_.)

(Readers knowledgeable about fexprs will note that they have been omitted from
this definition.  A discussion of fexprs and related objects appears at the
end of this Introduction.)

	In the above example, →(PLUS 1 2)_ is a form because it is a list whose
first element can be interpreted as the addition function and whose remaining
elements are atoms and hence forms.  →(PLUS 1 (TIMES 2 3))_ is also a form
because →(TIMES 2 3)_ is a form.  However →(1 2)_, though a list, is not a form
because 1 cannot be interpreted as a function.  Nor is →(PLUS 1 . 2)_, which is
not even a list.  On the other hand, →(QUOTE (PLUS 1 . 2))_ is a form despite
the fact that →QUOTE_'s argument is not a form.

Algebraic notation.  For programmers more comfortable with 1+2*3 than →(PLUS 1
(TIMES 2 3))_, most implementations offer a "front-end" that permits a certain
amount of algebraic notation for LISP programs.  There is as yet no generally
agreed-upon such notation for LISP programs however, so that these front-ends
vary sufficiently widely as to constitute separate programming languages.  For
this reason we shall present all programs in this article in the S-expression
notation, which is not only relatively standard but enjoys considerable support
amongst experienced LISP programmers.

Evaluation

	LISP programs are executed by a process called evaluation, which
given a form and an environment a collection of atoms together with their
bindings attempts to determine what the form denotes in
that environment.  That it is a process only becomes an issue when functions
are introduced into LISP that can permanently change the environment during
evaluation.  That part of LISP that cannot permanently change the environment
is sometimes called "pure" LISP.  One reason pure LISP is of interest is that
the pure LISP evaluator can be very easily defined as a function (called
→eval_) rather than as a process.  (We shall consider such a definition later.) 
When side effects are possible, the functional definition of →eval_ becomes
more awkward, having to acknowledge the importance of evaluating arguments in
order.  Another advantage is that reasoning about pure LISP programs can be
done "locally," that is, without having to consider possible unexpected
interactions between programs that do not directly call one another as
functions (modulo the remark on free occurrences of variables, in the section
on →LAMBDA_).

Properties of atoms

	Atoms may have properties.  We will discuss later mechanisms for
assigning properties to atoms.  For the moment we need mention only the
function →get[a,b]_ which given an atom →a_ and an indicator →b_ 
will return the value of the property of →a_ specified by →b_.  For
example, we may represent the fact that John's father is Fred by 
PUTPROP_.  Atoms may have properties.  →(PUTPROP a b c)_ assigns a its c
property, namely b.  Thus →(PUTPROP 'JOHN 'FRED 'FATHER)_ assigns →JOHN_ the
→FATHER_ property →FRED_.  The c part is called the indicator.

→GET_.  The function GET accesses properties.  Thus →(GET 'JOHN 'FATHER)_ will
return the →FATHER_ property of →JOHN_, which would be →FRED_ in the previous
example.

Use of properties.  In some implementations the value, printname (or pname) and
functional meaning of an atom are all stored on its property list under the
appropriate indicators, respectively →VALUE_, →PNAME_, and one of →EXPR_,
→FEXPR_, →MACRO_ or several other possible functional indicators.

LISP as a process-oriented language

	So far we have been able to describe LISP in terms of data and
functions.  This has made it possible for us to treat LISP more as a discipline
of mathematics than of programming.  What distinguishes programming from
mathematics are the notions of process, event, and change of state.  For
example, we have thus far considered →THE.FOX_ just to be an object, not the
process of constructing the pair →(THE . FOX)_.  We have considered →1+2_
to be simply →3_, not the process of adding →1_ to →2_ to get →3_.  We
now extend LISP to take the notion of process into account.

	Concretely, the notion of process appears in two important places in
LISP.  The first is the concept of assignment, the second flow of control. 
Assignment deals with several ways in which the state of the processor can be
changed.  Flow of control deals with determining which events happen and in
what order.

The LISP processor.  It is convenient to think of the evaluation of LISP
programs as taking place on a computer whose machine languge is LISP.  We shall
call this computer the LISP processor, or simply the processor.  The processor
has a state consisting of an environment (bindings of bound symbols), the
properties of all atoms, and a memory in which all list structures and arrays
are represented.  (Like any processor, a working model of such a thing will
also have many other aspects of its state, but these will all be invisible to
the user.  The idealized or abstract processor is just the visible part of the
whole machine, the tip of the iceberg.)

	The objective of the LISP processor is to take as input an
S-expression, and to yield as output the value of that S-expression.  That is,
the processor constitutes a definition of eval, no longer as a function but as
a process.  The processor will go through a sequence of states as it works
towards the answer.  The value of any given S-expression may vary from one
state to the next, the most obvious example being the value of →X_ as the
binding of →X_ changes from one value to another.

Assignment.  A number of operations exist to bring about state changes in every
aspect of the state.  Associated with the environment is →SET_ (together with
its very convenient variant →SETQ_).  Associated with properties is
→PUTPROP_ (with the convenient variant →DEFPROP_ in some implementations).
Associated with the state of →cons_ cells are →RPLACA_ and →RPLACD_. 
Associated with arrays is →STORE_.

→SET_ and →SETQ_.  Evaluation of →(SET a b)_ results in the binding of →aλ↑_
becoming →bλ↑_.  Thus evaluating →(SET 'X 3)_ will set the symbol →X_ to
→3_.  The value of →(SET a b)_ is →bλ↑_.

→RPLACA_ and →RPLACD_.  We have already mentioned the predicate →eq_, which
tests whether its two arguments do not merely represent the same object but in
fact are the same representation in that they are stored at the same location. 
It does this by testing the pointers to the respective locations for equality,
which in most computers can be done with a single instruction.  When the object
pointed to is a cell, containing a →car_ and a →cdr_, another similarly
convenient operation is thatob sToring a value in either the →car_ or the
→cdr_ part of the cell.  The effect is that future accesses of the →car_or
→cdr_ ob that cell wilh yield the new value stored there.  The two operations
for achieving this are →RPLACA_ and →RPLACD_ respectively.  The side effect of
evaluating →(RPLACA c v)_ is to store the value of →v_ in the →car_ half of the
cell given (pointed to) by the value of →c_.  In addition it returns as its
value the value of →c_.  →RPLACD_ does the same thing with →cdr_ instead of
→car_.

----MORE TO COME LATER-----

RPLACA RPLACD SET SETQ STORE

Control Functions:
EVAL GO 
PROG RETURN

Input-Output functions:
PRINT READ READCH (or READC) TERPRI

The EXPR-FEXPRdistinction.

	So far we have assumed thatthe evaluation of a form →(F X1 ... Xn)_
always begins with the evaluation of →X1_ through →Xn_, with the exceptions of →COND_
and →QUOTE_.  For some functions however, such evaluation often does nothing
more than strip off a →QUOTE_ from some quoted S-expression.  For example,
almost invariably →SET_ is used thus: (SET (QUOTE X) a) where X is an atom and
a the value that X is to be bound to.  To save on the use of quotes, it would
nice to have a version of SET that did not evaluate its first argument.  LISP
offers →SETQ_, with just this property, allowing the above example to be
written (SETQ X a).

	The mechanisms for dealing with such functions vary between
implementations.  In LISP 1.5 it
depends on how the car of a form (call the form F) is interpreted as a
function.  If the car of F is an atom, then the property list of that atom is
searched for a functional property.  For conventional functions the indicator
is EXPR.  For functions whose arguments are not to be evaluated, it is FEXPR. 
The FEXPR property must be a function of one or two arguments.  If it is a
function of one argument, then that function is applied to the cdr of F.  If it
is a function of two arguments it is applied to the cdr of F and the current
environment.



2. 	Language Design Issues in LISP

-----?????-----

	3.	The Mathematics Underlying LISP

	LISP borrows more heavily than any previous language from the
elegant yet powerful concepts that had evolved in the world of mathematical
logic in the last hundred years.  These concepts included:

	Abstract objects
	The pairing function as a universal data constructor
	Functions defined by lambda-abstraction
	Recursively defined functions

Abstract objects.  The concept of an abstract object is at least as old as the
concept of a number divorced from its representation.  Essentially all
high level programming languages embody the notion of abstract
numbers, whether or not they attempt to hide the representation by
forbidding representation-dependent operations (e.g. shifts and
Boolean operations on a binary machine).  They do this by allowing the
programmer to forget about the representation of the number If he
chooses and to imagine that he is manipulating only the abstracTions. 
The test for whether complEte liberation from the representation has
been attained is whether the object in question can be passed around
inside the computer in all possible ways.  An abstract object can:

 1.  be assigned to some variable;
 2.  be passed as an actual parameter of some procedure or function;
 3.  be returned as the value of some function.

	For example, in ALGOL, integers, reals and Booleans satisfy
all three tests and so are truly abstract objects.  (To judge from the
programming styles apparent in the early years of CACM's algorithms
department, the idea of Booleans as abstract objects was clearly a
difficult thing for people to come to grips with, and many programmers
continued to use two numbers, 0 and 1 usually, even though it was clear
that a Boolean was the appropriate data type.)  On the other hand, ALGOL
arrays fail tests 1 and 3, as do functions.  This restriction on arrays and
functions forced a clumsy programming style in ALGOL, as in most high level
programming languages of ALGOL's day; for example, the programmer could not
define a function that took as arguments two matrices and returned as value
their product.  Instead he had to write a procedure that took as arguments
three matrices, and arrange for the procedure to store the product of the
first two arguments into the third.  To accomplish this required a further
complication involving the distinction between parameters called-by-value
and parameters called-by-name, so that the programmer had to have the third
argument called-by-name.  (To add insult to injury, in most implementations
he also had to call the first two arguments by name to avoid pointless
inefficiency in making copies of the arrays, a problem caused by the
difficulty of the compiler's telling whether a copy is necessary.)

	These tests were not spelled out until as late as 1968 in
connection with the programming language POP-2 developed by R.
Popplestone at the University of Edinburgh.  Popplestone applied these
three criteria together with a fourth (that objects always be testable for
equality) to identify what he called "first-class citizens" for which the
four tests constituted their "bill of rights."  (For the fourth test
Popplestone got around the problem of testing equality of complicated
objects like functions and circular lists by changing the usual notion of
equality to that of LISP's EQ predicate.  This is inconsistent with the
standard notion of equality of two abstract objects, for which no effective
implementation is possible in general for functions, and we have therefore
omitted Popplestone's fourth test.)  It is clear in hindsight that even
though these conditions had not been made explicit at the time LISP was
conceived, the initial version of LISP met them for many more of its data
types than had any previous language.

	The only other language in wide use to embody this principle
extensively is APL.  In APL arrays are treated as objects, to be operated on
like any other object.  They may be passed as arguments to functions, and
returned as the value of a function.   They may also be assigned to variables. 
Thus APL arrays can be seen to pass the first-class-citizen test, though not if
Popplestone's fourth criterion concerning equality is applied.  There is no
predicate in APL that directly tests the equality of two arrays, though it is
not hard for the user to define one.

Pairing.  The power of the pairing function (LISP's CONS) was recognized in
mathematics half a century before LISP was developed.  In this section we
shall write (CONS a b) as a.b, in the mathematical spirit of concise
notation for ubiquitous concepts.  In the introduction we simply postulated
CAR and CDR without further ado; however, if we wished to be truly
mathematically pedantic, we might more properly begin by observing the
basic property of CONS, that if a.b = c.d then a=c and b=d.  That is, a.b
is an object from which in principle a and b can be reconstructed. 
Contrast this with +, where a+b = c+d does not necessarily imply either a=c
or b=d, whence given the number 4+5 (i.e. 9) it is not possible to say for
certain whether this was arrived at as the sum of 4 and 5, 3 and 6 or any
other combination.  The importance of this "information-preserving"
property of CONS is that it leads to abstract objects thatcan function as
memories holding two independent objects.  The apparent limitation to two
objects disappears when it is realized that if a.(b.c) = d.(e.f) then a=d
and b.c=e.f, whence b=e and c=f.  So by using CONS twice we can construct a
three-memory object.  Continuing in this way we can in principle build
indefinitely large memories as abstract objects.  This of course is all
obvious without this pedantry, but it is of interest to note that we were
able to say this much about CONS without having to mention the "memory
accessing" functions CAR and CDR, which in this section, continuing in our
spirit of brevity, we may write as α and β, which of course satisfy α(a.b)
= a and β(a.b) = b.  

	An important application of CONS is in the construction of lists, a
data type that is "synthetic" in LISP in the sense that it is not given as
primitive but is defined using CONS.  An object called NIL is assumed
given, and is taken to denote the empty list.  Then a.NIL is taken to be a
list of length 1 whose only element is a.  The object a.(b.NIL) is a list
of length 2, with elements a and b, and so on.  In general, if L is a list
so is a.L, and a.L has length one more than that of L.  The decision to
begin with NIL as the CDR rather than as the CAR and to form a.L rather
than L.a is mainly a matter of convenience in the external representation
of lists in LISP, where a.(b.NIL) is written as (a b).

\-abstraction.  In 1936 A. Church introduced the notion of \-defined
functions.  The idea is that, while one might intuitively speak of "x/2" as
denoting a function of x, it seems to lack the property one expects of a
function that it can be applied to an object.  To deal with this, Church
introduced the terminology "\x.M", where if M is a function of x (in the
sloppy usage) then "\x.M" is a function (no longer of x particularly) in
the strict sense, just as "cos" and "log" are functions in the strict sense
and are not associated with any particular variable.  "\x" is considered as
a meta-operator called lambda-abstraction whose job is to abstract the "of
x" from "function of x."  Thus "x+1" denotes a function of x while "\x.x+1"
denotes just a function (the successor function).  Moreover, "\x.x+1"
denotes the same function as "\y.y+1", illustrating that lambda-abstraction
removes the significance of the choice of variable.  Similarly "\x.f(g(x))"
denotes the composition of f and g, "\x.1" denotes the constant function
that returns 1 no matter what it is applied to, "\x.x*x*x" denotes the
cubing function, and so on.  Moreover, the arguments could themselves be
functions, allowing the creation of functionals (functions of functions),
for example "\f.(\x.f(f(x)))" which denotes the functional which, given a
function "f" returns a function corresponding to applying "f" twice.

	McCarthy adapted Church's \-notation to LISP, generalizing it to
several variables.  This gave the programmer the power to create, as
abstract objects, new functions from old, just as in Church's system. 
Unfortunately, nested lambda-abstractions, as in the "twice" example above,
were not catered for, losing much of the power of Church's version.

Recursively defined functions.  The story is often told (in one form or
another) of the mathematician who was asked "How do you boil an egg?"  He
replied, "Get a pan, fill it with water, place the water on the stove,
light the stove, wait till the water bubbles, put the egg in, wait three
minutes, then remove the egg."  Then he was asked "How do you boil water?"
to which he replied, "Get an egg, reducing it to the previous problem."  If
nothing else there is a compelling clarity of thought expressed in that
solution, and mathematicians have used the idea of reducing one problem to
another in many situations, particularly in definitions where one thing is
defined in terms of another.  In its most powerful form, an object may be
defined in terms of itself, or recursively, which may lead to a whole
series of reductions as the definition gets used over and over again.  If
the definition is worded sufficiently carefully these reductions will not
continue for ever but will terminate.

-----MORE TO COME-----

	4.	Program Verification in LISP

	Because of pure LISP's use of ideas from mathematical logic, it is very
easy to prove a variety of properties of pure LISP programs.  Let us begin by
proving that if →append_ is defined as "→a@b = if null a then b else
car[a].[cdr[a]@b]_," →a@[b@c] = [a@b]@c_ then for all lists →a_ and →b_
and all objectives (whether S-expressions or not).  That is, →append_ defined
in this way is an associative operation.

	In our proof it will be convenient to decompose conditionals into their
respective cases.  In the definition of →append_, either the list →a_ is
→NIL_, in which case the definition simlifies to
	→NIL@b = b_		(1)
or the list →a_ is non-→∀⊗↔_ in which case we may write →a_ as →x.y_
and the definition simplifies to
	→[x.y]@b = x.[y@b]_	(2).

	We shall prove this associativity result first of all for the special
case when →a_ is the empty list →NIL_.
	→a@[b@c] = NIL@[b@c]		(a=NIL)
		 = b@c			(by (1))
		 = [NIL@b]@c		(by (1))
		 = [a@b]@c		(a=NIL).  (3)

	Now let us prove it for any list →a_ of length 1, which we can always
write as →x.NIL_.
	→a@[b@c] = [x.NIL]@[b@c]
		 = x.[NIL@[b@c]]		(by (2))
		 = x.[[NIL@b]@c]		(by (3))
		 = [x.[NIL@b]]@c		(by (2))
		 = [[x.NIL]@b]@c		(by (2))
		 = [a@b]@c			    (4)

	Notice how we made use of the result (3) for the case ka=NIL_.  This
technique allows us to move on to lists of length 2, which we can express as
→x.y_ where y is a list of length 1.  If we carry out the above proof with
→NIL_ replaced by →y_ and the third line attributed to (4) instead of (3),
we will then have proved the result for all lists of length 2.

	It should be clear now that, having proved the result for lists of
length →n_, where →n_ is any non-negative integer, we can immediately use
the fact in a proof for lists of length →n+1_, just by expressing the list
→a_ of length →n+1_ as →x.y_ where →y_ is of length →n_ and using the
same proof over again.  In this way we can go on to prove the result for lists
of any length we care to name.  In fact, if we take the infinite set of all
such results, then we are entitled to infer from that set that the result holds
for all lists.  This step in the reasoning, from the infinitely many results,
(one for each length of list) to the single result for all lists, is called the
omega rule.  In general, if you have proved the infinitely many facts P→[0]_,
P→[1]_, P→[2]_,... (the antecedents) then you may infer the fact P→[n]_
(the consequent) wehre →n_ is not constrained to be any particular number. 
In our case P→[n]_ ws "for all lists →a_ of length →n_, →a@[b@c] =
[a@b]@c_." 

	In practice of course you never get around to applying the omega rule
because you never finish generating all of its antecedents.  Such infinitary
rules are of little real use.  What is needed is a means of looking tinto the
future, so to speak, and predicting that with infinitely much time you could
prove all of the antecedents.  One of the simplest reasons for being sure of
such a thing is you having a proof of P→[0]_, and also a proof of P→[n+1]_
that appeals to P→[n]_.  A proof step based on this reason is said to use the
induction rule.

	One can imagine a little engine that, once running and left alone, will
continue to run forever.  This corresponds to the part of the proof step that
establishes P[n+1] provided P[n] holds.  This part is called the inductive
step, and P[n] the induction hypothesis.  In order to get this engine to run
forever, it first has to be started.  This corresponds to the part that
established P[0], called the basis for the induction.




	5.	Implementation

	The degree of difficulty of implementing a programming language
depends largely on the extent of the difference between the implemented
language and the implementation language.  We shall begin with a very
abstract notion of an implementation language, consisting simply of some
carefully chosen mathematical functions, and later consider more
down-to-earth machine languages.

	Let us assume that we are given the domain of S-expressions, along
with certain functions and predicates on that domain.  Some of those
functions (whose LISP names are PLUS, TIMES, etc) are the sort of function
that a computer's machine language might already provide.  The functions
CONS, CAR and CDR, and the predicates EQ and ATOM are functions
which, though not expLicitly offered in the machine language, are nevertheless
not dificult to implement, with the excep@QS←\A=H	α∞|rMβ'rβS#∃∧+[↔;"βS#π h+K↔≡cπ7π&K?9β|1βπ∞s∪?;.!β7↔n{Keβf{∂πSN{;MβO→β∪↔≡KK↔⊃r↓α←∃π;'31εOOWn)βS#∂!β↔π≡@4+π&{5α→π##πQεkπeβf+∨'SNkπS↔gIβπCε+πIβNqβS#*β≠W;∨#'?9πβ?O'&K?9β}1βπ9¬→7↔cπ∪↔OON{84+O→βπO≤{∂'π&+⊃β←O#!βO}k∃βO,≠!β≠.s∂S'}qβ?IπβK↔∪N≠πS∃ε1β←#␈≠∃β'oβ3↔7.sSπSN{9β#∂_4+.+9βS∞[↔9β≡K∃β}1β?;*β←πeε{Iβπv{S#↔∩q↓α←*βπ3OzβπOO.k∃βSFQβ←*β#π[(h+↔;6KK?;n+;SMZβπ9β.s['K}s7↔;"β'Mβ
β≠W;∨#'?9ε3K?5π3πK'∞∪3↔MαC%;∃rβOg7⊗{3M0non-numeric atoms) to S-expressions, together with a mechanism for producing
new environments from old, namely [X:=a]e, which denotes the environment that
differs from e only in that the value of the variable X is a rather than e(X). 
Finally we have the function eval, which given an S-expression together with an
environment e returns the value denoted by that S-expression in that
environment.  We require eval to satisfy the following equations.  (We shall
use upper case letters to denote S-expressions, lower case to denote all other
objects.)

 eval[N,e]	=   N		where N is a number
 eval[V,e]	=   e(V)	where V is a variable
 eval[(F A1 ... An),e]		where F is a symbol with function f
		=   f(eval[A1,e],...,eval[An,e])
 eval[((LAMBDA (X1 ... Xn) B) A1 ... An),e]
		=   eval[B,[X1=eval[A1,e]][...][Xn=eval[An,e]]e]
 eval[(COND (A1 B1) ... (an Bn)), e]
		=   eval[Bi,e] where i is the least such that
				eval[Ai,e] is non-null
 eval[(QUOTE A)]=   A

	This definition is the "no-side-effects" definition.  It is
appropriate for that subset of LISP that excludes PUTPROP, SETQ, RPLACA and
RPLACD.

-----THERE IS MORE-----

	6.	Comparison with other languages

T

	7.	LISP - Past, Present and Future

	The peculiar names of the accessing functions refer to the two
fields in a word of the IBM 704, the host for the original implementation
of LISP.  These fields were the Contents of Address Register (CAR) and
Contents of Decrement Register (CDR).

-----ETC-----

-----THINGS TO MENTION SOMEWHERE-----

Organization of LISP programs

	Complex LISP programs are generally decomposed into a series
of function definitions which may either be typed directly to LISP or
entered off-line (usually via the computer#s file system and editing
program) and loaded into LISP.  Once loaded, a program is invoked by
the user's calling one of the functions.

	This section discusses the data types available in LISP.   The
following may not be found all together in any one implementation of LISP,
but most implement

-----

	numbers		integers (unlimited size), reals
	bit vectors	various applications, e.g. PASCAL's sets
	booleans	T and NIL (for false)
	atoms		serving double duty as strings and variables
	lists		for which LISP is best known
	property lists	various applications, e.g. PASCAL's records
	arrays		unrestricted as to type or dimension
	function(al)s	using LAMBDA and APPLY
	programs	using EVAL and QUOTE

-----

MUDDLE, ECL, etc
Use of property lists to implement cases - for both interpreter & user
Idea of doing all hashing when you read in the data
Interpreter vs compiler

-----

  Possible improvements to LISP

Give functions first-class-citizen status. (Without it, metatheory harder to do
cleanly; APPLY, *APPLY or FUNCALL made necessary for variables of type
function; funarg problem easily overlooked.)

Programs presently considered to denote themselves at read-in time.  Should
be considered to denote their values.  Apart from giving a cleaner semantics to
READ, this would give the user more power in writing data.

Use of S-expression notation for programs departs from conventional notation
unnecessarily.  A better scheme would be to have standard notation (f(x,y)
for most functional application, a few infix operator "glyphs" for essential
functions (+,-,*,/,**,.(cons),@(append)), lists inside brackets so that
parentheses can be used in their usual role of disambiguation, semicolon as a
statement separator, and parentheses only when needed for disambiguation.

EVAL is both a simplifier and a quote-stripper.  These jobs should be
separated.

Competence (what the program accomplishes) and performance (how it goes about
accomplishing it) should be separated better.  One particularly offensive
example in LISP is that of giving several names to the same function or
datatype as a means of supplying implementation information.  For example, a
near-alias of REVERSE, NREVERSE, exists primarily for the sake of efficiency.
Having a side-effect, it is not quite REVERSE, but the side-effect is scarcely
desirable.  Also the implementation of lists is taken too literally.  As a
result, random access to lists is invariably considered inefficient, prompting
the introduction of arrays, which semantically are redundant, and besides which
are not given first-class-citizen status in most implementations.  It would be
better to treat lists as one-dimensional arrays and deal with efficiency issues
in a separate part of the program.  While this could be done by having the
programmer give explicit advice that is physically separate from his program,
it may be worth pursuing the automation of such efficiency.  Taking the same
idea even further, it might be worthwhile combining the datatypes list and
function, treating a list as a function with domain an initial segment of the
natural numbers.

------
FONT 31VR, PRATT;BB, 31VRI
VSP 6 FSP 31 PAG 1 ULS ↓α ULE ↓
MAP \:λ, →:↓↓, _:↓
TECOXCT 79FSADLINE}W :↑I}EXIT}/70FSADLINE}/